package com.example.swordkotlin

import com.example.swordjava.Test8

object Test8 {

    @JvmStatic
    fun main(args: Array<String>) {
        val pre = intArrayOf(1, 2, 4, 7, 3, 5, 6, 8)
        val vin = intArrayOf(4, 7, 2, 1, 5, 3, 8, 6)
    }

    class TreeLinkNode(var `val`: Int) {
        public var left: TreeLinkNode? = null
        public var right: TreeLinkNode? = null
        public var next: TreeLinkNode? = null
    }

    /**
     * 给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。
     * */

//    var arrayList = ArrayList<TreeLinkNode>()
//    fun GetNext(pNode: TreeLinkNode): TreeLinkNode {
//        var root = pNode
//        while (root.next != null) {
//            root = root.next!!
//        }
//        inOrder(root)
//        for (i in arrayList.indices) {
//            if (pNode === arrayList[i]) {
//                return arrayList[i + 1]
//            }
//        }
//        return null
//    }
//
//    fun inOrder(treeLinkNode: TreeLinkNode?) {
//        if (treeLinkNode != null) {
//            inOrder(treeLinkNode.left)
//            arrayList.add(treeLinkNode)
//            inOrder(treeLinkNode.right)
//        }
//    }

    var linkNodes = ArrayList<TreeLinkNode>()

    fun GetNext(pNode: TreeLinkNode): TreeLinkNode? {
        var root = pNode
        while (root.next != null) {
            root = root.next!!
        }
        inOrder(root)
        for (i in 0 until linkNodes.size - 1) {
            if (linkNodes[i] === pNode) {
                return linkNodes[i + 1]
            }
        }
        return root
    }

    fun inOrder(treeLinkNode: TreeLinkNode?) {
        if (treeLinkNode != null) {
            inOrder(treeLinkNode.left)
            linkNodes.add(treeLinkNode)
            inOrder(treeLinkNode.right)
        }
    }
}